package 排序.demo;

import cn.hutool.core.util.ArrayUtil;

import java.util.Arrays;

public class 快速排序 {
    public static void main(String[] args) {
        int[] arr = new int[]{6, 67, 2, 3, 8};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.printf(i + "\t");
        }
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low <= high) {
            int pivot = getPivot(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    public static int getPivot(int[] arr, int low, int high) {
        int key = arr[low];
        int l = low, h = high;
        while (l < h) {
            while (l < h && arr[h] >= key) {
                h--;
            }
            while (l < h && arr[l] <= key) {
                l++;
            }
            if (l < h) {
                swap(arr, l, h);
            }
        }
        swap(arr, low, l);
        return low;
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
